/**
 * Created with IntelliJ IDEA.
 *
 * @Auther: 邹陆川
 * @Date: 2022/04/19/10:03 上午
 * @Description:基于链表实现符号表
 */
public class SymbolTable<Key,Value> {
  private Node head;//头节点
  private int N;//表长度
  //内部节点类
  private class Node{
    private Key key;//存储键
    private Value value;//存储值
    public Node next;//下一个节点

    //构造方法
    public Node(Key key, Value value, Node next) {
      this.key = key;
      this.value = value;
      this.next = next;
    }
  }
  public SymbolTable(){
    this.head = new Node(null,null,null);
    this.N = 0;
  }


  //返回表长度
  public int size(){
    return this.N;
  }
  //向符号表中插入健值对
  public void put(Key key,Value value){
    //拿到首节点
    Node n = this.head;

    while(n.next != null){
      //判断是否存在此key
      if(key.equals(n.key)){
        //覆盖值
        n.value = value;
        return;
      }
      //下一个
      n = n.next;
    }
    //未存在
    //先得到当前头节点
    Node n2 = this.head.next;
    //新节点的下一个节点指向原来头节点
    Node node = new Node(key, value, n2);
    //头节点指向新节点
    this.head.next = node;
    this.N ++;
    //
  }
  //根据key删除元素
  public void delete(Key key){
    //拿到首节点
    Node n = this.head;
    while(n.next != null){
      //判断是否存在此key
      if(key.equals(n.key)){
        //将key对应的下一个节点指向下下个节点
        n.next = n.next.next;
        this.N --;
        return;
      }
      //下一个
      n = n.next;
    }
  }
  //根据key得到元素
  public Value get(Key key){
//拿到首节点
    Node n = this.head;
    while(n.next != null){
      //判断是否存在此key
      if(key.equals(n.key)){
        //返回值
        return n.value;
      }
      //下一个
      n = n.next;
    }
    return null;
  }
}
